# JZ3 从尾到头打印链表
#
# 描述
# 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
# 如输入{1,2,3}的链表:
# 返回一个数组为[3,2,1]
# 0 <= 链表长度 <= 10000
#
# 示例1
# 输入：
# {1,2,3}
# 返回值：
# [3,2,1]
# 示例2
# 输入：
# {67,0,24,58}
# 返回值：
# [58,24,0,67]

# -*- coding:utf-8 -*-
# 核心代码模式
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):  # 链表类型
        # write code here
        if not listNode:
            return []
        # 方法一辅助数组
        res = []
        # 思路一正序存储反序打印
        while listNode:
            res.append(listNode.val)
            listNode = listNode.next
        return res[::-1]

        # 方法二 到链表尾部递归
        # 思路二 反序存储直接打印
        res = []
        if not listNode:
            self.printListFromTailToHead(self, listNode)
            res.append(listNode.val)
        return res

        # 方法三 栈 先进后出
        if not listNode:
            return []
        # 辅助栈存链表，pop到辅助数组输出
        stack = []
        res = []
        while listNode:
            stack.append(listNode.val)  # 进栈
            listNode = listNode.next
        while stack:
            res.append(stack.pop())  # 出栈
        return res
